/**
 * Created with IntelliJ IDEA.
 * Description: KMP算法实现.
 * User: 86187
 * Date: 2022-10-05
 * Time: 18:53
 */
public class TestKMP {
    /**
     * @param str 主串
     * @param subStr 子串
     * @param pos 从主串的pos位置开始匹配
     * @return 找到子串在主串当中的下标
     */
    public static int KMP(String str, String subStr,int pos) {
        if(str == null || subStr == null) return -1;

        int strLen = str.length();
        int subStrLen = subStr.length();
        if(strLen == 0 || subStrLen == 0) return -1;

        if(pos < 0 || pos >= strLen) return -1; //pos的合法性

        // 求next数组
        int[] next = new int[subStrLen];
        getNext(subStr,next);
        // 优化后的nextVal数组
        // 1. 回退到的位置和当前字符一样,就写回退的那个位置的nextVal值
        // 2. 回退到的位置和当前字符不一样,就写当前字符原来的next值.

        int j = 0; //遍历子串
        int i = pos; //遍历主串

        while(i < strLen && j < subStrLen) {
            // j == -1 时,一开始就匹配失败
            if(j == -1 || str.charAt(i) == subStr.charAt(j)) {
                ++i;
                ++j;
            } else {
                j = next[j]; // next数组.
            }
        }
        if(j >= subStrLen) return i-j;
        return -1;
    }

    private static void getNext(String sub,int[] next) {
        next[0] = -1;
        if(next.length == 1) return;

        next[1] = 0;
        int k = 0; //前一项的k
        int i = 2; // 提前走了一步
        // 遍历子串
        for(;i < sub.length(); ++i) {
            if(k == -1 || sub.charAt(i-1) == sub.charAt(k)) {
                next[i] = ++k;
            } else {
                k = next[k];
                // KMP核心是i不回退, k回退,在k回退的过程中,i应该不动
                // 所以有了以下的--i,来抵消循环的++i操作. 或者可以改为while循环
                --i;
            }
        }
    }
    
    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        System.out.println(KMP("ababcabcdabcdeabcdef", "abcd", 0)); // 5
        System.out.println(KMP("ababcabcdabcdeabcdef", "abcdf", 0)); // -1
        System.out.println(KMP("ababcabcdabcdeabcdef", "abcde", 0)); // 9
        System.out.println(KMP("ababcabcdabcdeabcdef", "abcdef", 0)); // 14
        System.out.println(KMP("ababcabcdabcdeabcdef", "ab", 0)); // 0
        System.out.println(KMP("abcababcabcdef", "abcababcabc", 0)); // 0
        long endTime = System.currentTimeMillis();
        System.out.println("优化next数组前耗时: " + (endTime - startTime) + "ms");

    }
}
